package main

import (
	"fmt"
)

const N = 5 // 元素的个数
const W = 6 // 背包的大小

var weight []int = []int{3, 1, 2, 4, 6} // 元素的大小
var val []int = []int{9, 3, 2, 6, 13}   //元素的价值

var dp [N + 1][W + 1]int //动态规划网格

//i是已经有的重量，total总量
func solve2() int {
	length := len(val)
	for i := 0; i < length; i++ {
		for j := weight[i]; j <= W; j++ {
			dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+val[i])
		}
	}
	fmt.Println(dp)
	return dp[N][W]
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {
	fmt.Println("背包问题动态规划")

	fmt.Println(solve2())
}
